1. Field of the Invention
The present invention relates to electronic devices, and, more particularly, to fault and noise tolerant devices made of aggregations of locally-interacting cells.
2. Description of the Related Art
Growth in the semiconductor industry has been a strong function of the density of on-chip computational resources. Much of current semiconductor research is motivated by the inherent advantages in terms of cost reduction and performance enhancement associated with reducing minimum circuit geometries. For example, the increasing capacity of dRAMs reflects this cost pressure; see H. Sunami, Cell Structures for Future DRAM's, 1985 IEDM Tech. Digest 694-697.
Further reductions in on-chip functional density are inhibited by the saturation of interconnect density and the degradation of device properties as local, interdevice coupling becomes a dominant interaction in scaled systems. The speed and functional density VLSI is now limited by the number and size of the interconnections between gates. Device densities are now reaching the point where classical notions of isolated, functionally independent active elements are giving ground to a highly coupled, quantum mechanical perspective. There is no clear method available that permits the continued downscaling of active elements (and their connections) beyond evolutionary limits.
Basic problems brought on by further downscaling include; unavoidable interdevice crosstalk, interconnect crosstalk, interconnect RC time-constant effects, and the breakdown of classical "transistor" properties in the ultra-submicrometer regime. Furthermore, as the number of electrons that participate in each basic process decreases with scaledown, errors induced by substrate defects, cosmic rays, and thermal fluctuations become more significant. These hardware dilemmas suggest that further increases in the density of on-chip computational resources will require computer architectures that are compatible with future semiconductor technologies, take account of device faults and strong inter-device coupling, and emphasize a reduction in device-level connectivity. Cellular automata may provide the basis for such architectures.
Cellular automata are generally n-dimensional arrays of cells, together with a fixed, local rule for recomputing the value associated with each cell from the values of the neighboring cells. Cellular automata were originally proposed by John von Newmann as mathematical models to study self-replication; see, A. Burks, Ed., Essays on Cellular Automata (Illinois Press, 1970). More recently, they have been considered as possible models of general nonlinear phenomena such as turbulence, and have been used for nonlinear image processing in the biomedical and pattern recognition fields; see, K. Preston et al, Basics of Cellular Logic with Some Applications in Medical Image Processing, 67 Proc. IEEE 826 (1979). Further, cellular automata have the same structure as an FIR filter, but using a general update rule rather than arithmetic, and are suitable models for studying highly parallel, pipelined computation structures for digital signal processing. Also, they can simulate the action of an arbitrary Turing machine and thus are capable of universal computation; see references in K. Steiglitz et al, A Multi-Processor Cellular Automaton Chip, 1985 ICASSP 272.
In principle, a variety of cellular automata can imitate all of the logical operations required of a general purpose computer; see A. Burks Ed., Essays on Cellular Automata (Illinois Press 1970), D. Farmer et al, Cellular Automata (North-Holland Physics Publishing, Amsterdam 1984) and E. F. Lodd, Cellular Automata (Academic Press 1968). Importantly, local-only communication dramatically improves the chances for scaling the architecture since the movement of information between computations is controlled locally. Next-generation device technologies will require the downscaling of active electronic devices to fundamental physical limits. To be successful, devices with revolutionary scalability will require an equally scalable architecture such as cellular automata. Finally, we note that current research into improving digital signal processing (DSP) algorithms is establishing the usefulness of decomposing complex, existing DSP functions into simple, modular, massively parallel sub-functions. For this special class of computation, a fractal architecture, wherein all levels of functionality are structured like systolic cellular automata, may be ultimately the most efficient architecture. Therefore, interest in developing architectures based on cellular automata is prompted by the limits of current practice, the trends in special purpose computation, and the compatibility requirements of next-generation technology.
Previous cellular automaton research has concentrated on their use to simulate the behavior of physical systems; see, generally, D. Farmer et al, Cellular Automata (North-Holland Physics Publishing, Amsterdam 1984). Relatively little effort has been devoted to the understanding, design, and characterization of cellular automata as potential machines for computation. Only the simplest, one-dimensional "line" automata have been studied in any detail. The complex activities associated with multi-dimensional cellular automata remain largely unexplored. Existing models do not yet provide practical, or comprehensive computational solutions. What is required are constructions that can execute both general purpose and problem specific algorithms at high speed, while accounting for the practical problems of ultra-downscaled circuits such as the sensitivity to electrical noise in these components.
No real multistate machine can be fault free. This conclusion follows from thermodynamics. However, there are two approaches that provide essentially error-free hardware in a thermal world. In the first method, the system can be designed using components that are collectively so reliable that soft (dynamic, recoverable) errors are assumed to occur after the mean time before failure of any component. Hard (fixed) errors are preempted by preventative hardware replacement. The second scheme assumes a reasonable distribution function for soft errors over time and invokes a strategy to detect and correct errors as they occur. For a theoretical treatment of fault detection in systolic arrays, see A. Vergis and K. Steiglitz, Testability Conditions for Bilateral Arrays of Combinational Cells, 35 IEEE Trans. Comp. 13 (1986).
A system will be fault tolerant insofar as several input states or signals are mapped by information-dissipative operations into the same output state or signal. As noise is usually statistically uncorrelated, practical fault tolerance requires that noise-induced bifurcations in state trajectory during a computation or memory operation, brought about by random noise, will remain mappable into the desired output state sequence. It should be stressed that shrinking design rules will only exacerbate the problem of signal-to-noise ratio reduction in computing machines. Therefore, functions based upon the probabilistic nature of ultra-submicrometer quantum devices must include self-repair and fault tolerance as basic design considerations.
State machines such as cellular automata may be, but are not always, very sensitive to noise. In a cellular automaton an input state, which is globally defined by the individual cell values, evolves over time to generate new spatio-temporal output states. In many cases, the alteration of a single cell value results in very different system dynamics. Such cases are characterized by a poor tolerance to either faults in the cell operation or noise in the initial input conditions.